Teoria de la complexitat computacional
La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un algorisme.
Es considera que un problema és inherentment difícil si la seva solució requereix recursos importants, sigui quin sigui l'algorisme utilitzat. La teoria formalitza aquesta intuïció, introduint models matemàtics de càlcul per estudiar aquests problemes i quantificant-ne la complexitat computacional, és a dir, la quantitat de recursos necessaris per resoldre'ls, com el temps i la necessitat d'emmagatzematge. També s'utilitzen altres mesures de complexitat, com ara la quantitat de comunicació (utilitzada en complexitat de comunicació), el nombre de portes en un circuit (utilitzat en complexitat de circuits) i el nombre de processadors (utilitzat en informàtica paral·lela). Una de les funcions de la teoria de la complexitat computacional és determinar els límits pràctics del que els ordinadors poden i no poden fer. El problema P versus NP, un dels set problemes del Premi del Mil·lenni, està dedicat al camp de la complexitat computacional.[1]
Camps estretament relacionats en la informàtica teòrica són l'anàlisi d'algorismes i la teoria de la computabilitat. La primera es dedica a analitzar la quantitat de recursos que necessita un algorisme en particular per resoldre un problema, mentre que la segona fa una pregunta més general sobre tots els possibles algorismes que es podrien utilitzar per resoldre el mateix problema. Més concretament, la teoria de la complexitat computacional intenta classificar problemes que es poden o no resoldre amb recursos restringits adequadament. Al seu torn, imposar restriccions als recursos disponibles és el que distingeix la complexitat computacional de la teoria de la computabilitat: aquesta darrera teoria es pregunta quin tipus de problemes es poden, en principi, resoldre algorítmicament.
Referències
[modifica]- ↑ «P vs NP Problem | Clay Mathematics Institute» (en anglès). www.claymath.org. Arxivat de l'original el 2018-07-06. [Consulta: 23 octubre 2021].
Bibliografia
[modifica]- Arora, Sanjeev; Barak, Boaz. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 978-0-521-42426-4.
- Downey, Rod; Fellows, Michael. Parameterized complexity. Berlin, New York: Springer-Verlag, 1999. ISBN 9780387948836.
- Du, Ding-Zhu. Theory of Computational Complexity. John Wiley & Sons, 2000. ISBN 978-0-471-34506-0.
- Goldreich, Oded. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
- Handbook of theoretical computer science (vol. A): algorithms and complexity. MIT Press, 1990. ISBN 978-0-444-88071-0.
- Papadimitriou, Christos. Computational Complexity. 1st. Addison Wesley, 1994. ISBN 978-0-201-53082-7.
- Sipser, Michael. Introduction to the Theory of Computation. 2nd. USA: Thomson Course Technology, 2006. ISBN 978-0-534-95097-2.